package ai.zixing.mashibing.basic_class.class03;

public class Code03_PartitionAndQuickSort {

    public static int partition(int[] arr, int L, int R) {
        if (L > R) {
            return -1;
        }
        if (L == R) {
            return L;
        }
        int lessEqual = L - 1;
        int index = L;
        while (index < R) {
            if (arr[index] <= arr[R]) {
                swap(arr, index, ++lessEqual);
            }
            index++;
        }
        swap(arr, ++lessEqual, R);
        return lessEqual;
    }

    // arr[L..R] 玩荷兰国旗问题的划分 以 arr[R] 作为划分值
    // 返回等于区的左右边界
    public static int[] netherlandsFlag(int[] arr, int L, int R) {
        if (L > R) {
            return new int[]{-1, -1};
        }
        // 只有一个数，不用划分
        if (L == R) {
            return new int[]{L, R};
        }
        // 小于区域右边界
        int less = L - 1;
        // 大于区域左边界
        int more = R;
        // 数组下标
        int index = L;
        while (index < more) {
            // 相同则指针右移
            if (arr[index] == arr[R]) {
                index++;
            } else if (arr[index] < arr[R]) {
                // 扩大小于区右边界，并将当前下标于小于区右边界数交换，之后指针右移
                swap(arr, index++, ++less);
            } else {
                // 大于区左边界左扩
                swap(arr, index, --more);
            }
        }
        // 将arr[R] 交换到 大于区左边界
        swap(arr, more, R);
        return new int[]{less + 1, more};
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // M 为排好的数
    public static void process1(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        int M = partition(arr, L, R);
        process1(arr, L, M - 1);
        process1(arr, M + 1, R);
    }

    // [L,R] 内的是等值排好的
    public static void process2(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        int[] equalArea = netherlandsFlag(arr, L, R);
        process2(arr, L, equalArea[0] - 1);
        process2(arr, equalArea[1] + 1, R);
    }

    // [L,R] 内的是等值排好的
    public static void process3(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
        int[] equalArea = netherlandsFlag(arr, L, R);
        process3(arr, L, equalArea[0] - 1);
        process3(arr, equalArea[1] + 1, R);
    }
}
